package com.company.ljh.medium;
//给你一个字符串 s，找到 s 中最长的回文子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母组成
//
// Related Topics 字符串 动态规划
// 👍 4903 👎 0

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/3/21 14:12
 * @version:1.0
 */
public class 最长回文串 {
    /**
     * 双指针解法
     * 1.可能会以一个字符为中心，也可能以两个字符为中心
     * 2.时间复杂度n^2
     */

    public static String longestPalindrome(String s) {
        if ("".equals(s) || null == s) {
            return "";
        }
        char[] chars = s.toCharArray();
        //直接取一个字符作为回文串
        String longestSingleStr = getLongestStrBySingleCharacter(chars);
        String longestDoubleStr = getLongestStrByDoubleCharacter(chars);
        if (longestDoubleStr.length() > longestSingleStr.length()) {
            return longestDoubleStr;
        } else{
            return longestSingleStr;
        }
    }

    private static String getLongestStrByDoubleCharacter(char[] chars) {
        int maxSize = 1;
        String longestStr = String.valueOf(chars[0]);
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] != chars[i + 1]) {
                continue;
            }
            int size = 2;
            String str = chars[i] + "" + chars[i + 1];
            if (size > maxSize) {
                maxSize = size;
                longestStr = str;
            }
            for (int start = i - 1, end = i + 2; start >= 0 & end < chars.length; start--, end++) {
                if (chars[start] != chars[end]) {
                    break;
                } else {
                    size++;
                    str = chars[start] + str + chars[end];
                    if (size > maxSize) {
                        longestStr = str;
                        maxSize = size;
                    }
                }
            }
        }
        return longestStr;
    }

    private static String getLongestStrBySingleCharacter(char[] chars) {
        int maxSize = 1;
        String longestStr = String.valueOf(chars[0]);
        for (int i = 0; i < chars.length; i++) {
            int size = 1;
            String str = String.valueOf(chars[i]);
            for (int start = i - 1, end = i + 1; start >= 0 & end < chars.length; start--, end++) {
                if (chars[start] != chars[end]) {
                    break;
                } else {
                    size++;
                    str = chars[start] + str + chars[end];
                    if (size > maxSize) {
                        longestStr = str;
                        maxSize = size;
                    }
                }
            }
        }
        return longestStr;
    }

    public static void main(String[] args) {
        String str = "babad";
        String s = longestPalindrome(str);
        System.out.println(s);
    }
}
